#include<iostream>
#include<vector>
using namespace std;
/** Definition for a binary tree node. */
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
    TreeNode *root;
    Solution(){
        root = new TreeNode();
    }
    void binary(int i, int j, TreeNode *node,TreeNode* parent,vector<int>& nums){
        if(i>=j || i<0 || j>nums.size())
            return;
        int mid = (i+j)/2;  //二分的中间节点
        if(node==nullptr)   //创建一个新的节点
            node = new TreeNode(nums[mid]);
        else
            node->val = nums[mid];
        if(parent!=nullptr){    //挂载子节点
            if(node->val<=parent->val)
                parent->left = node;
            else parent->right=node;
        }
        binary(i,mid,node->left,node,nums); //继续二分
        binary(mid+1,j,node->right,node,nums);
        return;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        binary(0,nums.size(),root,nullptr,nums);
        return root;
    }
};
int main(int argc, char* argv[]) {
    vector<int>nums={-10,-3,0,5,9};
    Solution solution = Solution();
    solution.sortedArrayToBST(nums);
}